package com.banmao.CarlCamp.Day09;

public class LC19_Carl {

    // Carl 题解
    public ListNode removeNthFromEnd(ListNode head, int n) {
        // 又忘记了
        // 使用双指针可以提高空间复杂度
        // 快指针先走 n-1 步，之后快慢指针一起移动，当快指针指向末尾时，慢指针指向的节点就是需要删除的

        // 使用虚拟头可以减少特殊情况
        ListNode dummy = new ListNode(-1, head);
        //int slow = 0, fast = 0;
        ListNode slowN = dummy, fastN = dummy;
        while (n > 0) {
            fastN = fastN.next;
            n--;
        }
        // slowN 和 fastN 一起移动，直到 fastN.next 为空
        while (fastN.next != null) {
            slowN = slowN.next;
            fastN = fastN.next;
        }
        // 删除 slowN 的下一个节点
        slowN.next = slowN.next.next;

        return dummy.next;
    }

    private static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
